#include "LinkStack.h"
#include "DoubleLinkList.h"
#include "LinkQueue.h"
#include <iostream>
#include <ctime>

// size_t partition(int *array,size_t start, size_t end)
// {
//     size_t left = start;
//     size_t right = end;
//     int temp = array[start];
//     while(left < right)
//     {
//         while(array[right] > temp && left < right)      //array[right] > temp
//         {
//             right--;
//         }
//         if(left < right)
//             array[left++] = array[right];

//         while(array[left] < temp && left < right)       //array[left] < temp
//         {
//             left++;
//         }
//         if(left < right)
//             array[right--] = array[left];            
//     }
//     array[left] = temp;

//     return left;
// }

//借助栈实现非递归的快速排序
// void FastNoRecur(int *a, size_t start, size_t end)
// {
//     LinkStack s;  //存放区间的栈
//     s.Push((void*)start);
//     s.Push((void*)end);

//     while(s.IsEmpty() == false)  //栈不为空，还有区间需要排序
//     {
//         //取区间
//         size_t right = (size_t)*s.GetTop();
//         s.Pop();
//         size_t left = (size_t)*s.GetTop();
//         s.Pop();
//         size_t mid = partition(a,left,right);  //把区间传给分组排序
//         if(mid != 0 && left < mid - 1)
//         {
//             //左区间入栈
//             s.Push((void*)left);
//             s.Push((void*)(mid - 1));
//         }

//         if(mid + 1 < right)
//         {
//             //右区间入栈
//             s.Push((void*)(mid + 1));
//             s.Push((void*)right);
//         }
//     }
// }

// int main()
// {
//     LinkStack s;
//     for(size_t i = 0; i < 20; i++)
//     {
//         s.Push((void*)(i+1));
//     }

//     while(s.IsEmpty() == false)
//     {
//         std::cout<< *(int *)s.GetTop()<<" ";
//         s.Pop();
//     }
//     std::cout << std::endl;
//     return 0;
// }

// int main()
// {
//     int a[] = {4,1,5,2,7,3,9};

//     FastNoRecur(a,0,sizeof(a) / sizeof(a[0]) - 1);

//     for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
//     {
//         std::cout<<a[i]<<" ";
//     }
//     std::cout<<std::endl;
//     return 0;
// }

int main()
{
    LinkQueue q;
    for(long i = 0; i < 20; i++)
    {
        q.Push((void*)(i + 1));
    }

    while(q.IsEmpty() == false)
    {
        std::cout<<(long)*q.GetFront()<<" ";
        q.Pop();
    }
    std::cout<<std::endl;
    return 0;
}